import  sys
class Solution(object):
    # O(m+n)
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
    #     a = len(nums1)
    #     b = len(nums2)
    #     if (a+b)%2==1:
    #         return self.findK(nums1,nums2,(a+b)//2+1)
    #     else:
    #         return  (self.findK(nums1,nums2,(a+b)//2) + self.findK(nums1,nums2,(a+b)//2+1)) /2.0
    #
    #
    # def findK(self,a,b,k):
    #     la = len(a)
    #     # lb = len(b)
    #     # if la>lb:
    #     #     return  self.findK(b,a,k)
    #     if la==0:
    #         return b[k-1]
    #     if k==1:
    #         return  min(a[0],b[0])
    #     pa = min(k//2,la)
    #     pb = k-pa
    #     if a[pa-1] <= b[pb-1]:
    #         return self.findK(a[pa:],b,pb)
    #     else:
    #         return  self.findK(a,b[pb:],pa)

    def findMedianSortedArrays(self, nums1, nums2):
        # o(min(m,n))
        mins = -sys.maxsize
        maxs = sys.maxsize

        a = len(nums1)
        b =  len(nums2)
        if a>b:
            return  self.findMedianSortedArrays(nums2,nums1)
        if a==0:
            return  (nums2[(b-1)//2] + nums2[b//2])//2
        size = a+b
        cutl = 0
        cutr = a
        cut1 = a//2
        cut2 = size//2-cut1

        while cut1<=a:
            cut1 = (cutr-cutl)//2 + cutl
            cut2 = size//2 - cut1

            if cut1==0:
                l1 = mins
            else:
                l1 =nums1[cut1-1]

            if cut2==0:
                l2 = mins
            else:
                l2 =nums2[cut2-1]

            if cut1==a:
                r1 = maxs
            else:
                r1 =nums1[cut1]

            if cut2==b:
                r2 = maxs
            else:
                r2 =nums2[cut2]

            if l1>r2:
                cutr = cut1-1
            elif l2>r1:
                cutl = cut1+1
            else:
                if (size%2)==0:
                    l1 = max(l1,l2)
                    r1 = min(r1,r2)
                    return (l1+r1)/2.0
                else:
                    r1 = min(r1,r2)
                    return r1



a = [2,3,4,5]
b = [1]
# a = [1,3]
# b = [2,4]

s= Solution()
print(s.findMedianSortedArrays(a,b))